1. Field of the Invention
This invention relates to the design of digital logic systems and more particularly to the use of a hierarchically ordered library of canonical digital logic elements to facilitate the design of optimized digital logic systems.
2. Description of the Background Art
In the design of digital logic systems, the reduction of the logic equations to a hardware implementation is referred to as logic synthesis. This synthesis process consists of two discrete steps. The first step involves the optimization of the logic equations into a minimum number of realizable steps. Most digital equations expressed in boolean (binary logic) form are capable of multiple equivalent representations. This optimization process requires that the designer choose among the various forms of the boolean equation, that expression which may be implemented using the fewest gate delays and the least amount of geometrical area or component floor space.
The second step of the logic synthesis process consists of identifying digital components available to the designer which may be used to realize the optimized boolean equation. Each designer has a finite list of components available for implementing the target equation. These components are often stored as design cells in a computer aided design environment. The mapping process involves the substitution by the designer of cell components for terms in the optimized boolean equation. Complicating the efforts of the designer is the usual availability of a variety of cell design implementations from which the designer may choose to implement any given cell function. As the number of available cells in a cell library increases, the various possible implementations of an optimized boolean equation increases exponentially. As in the optimization step above, the designer must choose among the various cell realizations for the implementation which produces the fastest result while using the least amount of geometrical area to build.
A basic tenet of Boolean arithmetic is that any boolean equation may be realized using one or more appropriate combinations of inverters and two input NAND gates (NAND2). It should be noted that inverters and two input NOR (NOR2) gates work equally well, however, NAND2 gates are used throughout this specification to simplify the description. To implement an AND function, for instance, a NAND function is followed by an inverter. This construction of an AND gate using an inverter and a NAND2 gate is referred to as the "canonical form" of the AND function. Library cells consist of components designed and represented in their canonical form.
In order to implement the optimized Boolean function using canonical form cell components, the optimized Boolean function must first be decomposed into a canonical form net list. A typical canonical form net list 14 for a simple boolean equation is shown in FIG. 1. Once the net list 14 is decomposed into a canonical form, the various canonical logic subcomponents available in the cell library are compared with each section of the canonical net list to determine which of the cells will "map" or match with sections of the net list. This mapping of the cell library to the net list is generally very time consuming, particularly since most cell functions have multiple equivalent canonical representations. What is needed is a system for reducing the number of combinations of library cells and net list sections which must be checked.